package daily;

import java.util.Arrays;

public class Solution3233 {
    public static void main(String[] args) {
        Solution3233 solution = new Solution3233();
//        System.out.println(solution.nonSpecialCount(5,7));
//        System.out.println(solution.nonSpecialCount(4,16));
        System.out.println(solution.nonSpecialCount(1,2));
    }
    public int nonSpecialCount(int l, int r) {
        double tag = Math.sqrt(r);
        int[] prime = count((int)tag);
        int ans = 0;
        for (int i = 2; i < prime.length; i ++) {
            if (prime[i] == 0) {
                continue;
            }
            long val = (long) Math.pow(i, 2);
            if (l <= val && val <= r) {
                ans ++;
            }
        }
        return (r - l + 1) - ans;
    }

    // 统计 1-x之间的质数数量
    private int[] count(int x) {
        int[] prime = new int[x+1];
        Arrays.fill(prime, 1);
        for (int i = 2; i <= x; i ++) {
            if (prime[i] == 1) {
                if ((long) i * i <= x) {
                    for (int j = i * i; j <= x; j += i) {
                        prime[j] = 0;
                    }
                }
            }
        }
        return prime;
    }
}
